package sword.chapter8Tree;

/**
 * 从根结点到叶结点的路径数字之和
 *
 * 深度优先搜索 前序遍历，先操作的当前节点
 *
 * 技巧
 * 叶子节点判断 node.left==null node.right==null
 *
 * @author K
 * @date 2021/12/7 09:20
 */
public class S49SumNumbers {
    public static int s49(TreeNode root) {
        return dfs(root, 0);
    }

    private static int dfs(TreeNode root, int value) {
        if (root == null) {
            return 0;
        }
        int curValue = value * 10 + root.val;
        if (root.left == null && root.right == null) {
            return curValue;
        }
        int leftSum = dfs(root.left, curValue);
        int rightSum = dfs(root.right, curValue);
        return leftSum + rightSum;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode node9 = new TreeNode(9);
        TreeNode node0 = new TreeNode(0);
        TreeNode node5 = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        root.left = node9;
        root.right = node0;
        node9.left = node5;
        node9.right = node1;
        node0.right = node2;

        int result = s49(root);
        System.out.println();
    }
}
